#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int q[N], a[N];

int n, m;

int main()
{
	cin >> n >> m;
	
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	
	
	int hh = 0, tt = -1;
	
	for (int i = 0; i < n; i ++ )
	{
		while (hh <= tt && i - q[hh] + 1 > m) hh ++ ;
		while (hh <= tt && a[q[tt]] >= a[i] ) tt -- ;
		q[ ++ tt] = i;
		
		if (i >= m - 1) cout << a[q[hh]] << ' '; 
	}
	
	hh = 0, tt = -1;
	puts("");
	
	for (int i = 0; i < n; i ++ )
	{
		while (hh <= tt && i - q[hh] + 1 > m) hh ++ ;
		while (hh <= tt && a[q[tt]] <= a[i] ) tt -- ;
		q[ ++ tt] = i;
		
		if (i >= m - 1) cout << a[q[hh]] << ' '; 
	}
	
	return 0;
	
}